The present invention relates to navigation technology. More particularly, it relates to an in-vehicle navigation system which searches for a recommendable path complying with a given final destination, and which teaches the driver of a vehicle the current position of the vehicle and the traveling direction thereof along the recommended path.
Techniques for searching a recommendable path extending from a point of departure (namely, an origin or a starting point) to a destination point, have been known from the official gazette of Japanese Patent Application Laid-open No. 306400/1990, and a paper entitled "Path Search Algorithm based on Hierarchical Expression of Road System and Application to Map Information Processing System" (Bulletin of the Japan Institute of Information Processing, Vol. 32, No. 5, pp. 659-666, March 1990).
As illustrated in FIG. 14A, the technique disclosed in the official gazette of Japanese Patent Application Laid-open No. 306400/1990 divides a map into unit areas each having predetermined size and shape (into individual square cells shown in the figure) and it makes a path search based upon the map data of the unit areas. Herein, when the point of departure and the destination point exist in different unit areas path search is made by setting any of the following as a search area (an area to-be-searched):
(1) Unit areas which are traversed by a straight line joining both the points;
(2) Unit areas which are traversed by a straight line joining both the points, and unit areas which adjoin the former unit areas;
(3) Among unit areas traversed by a straight line joining both the points and the unit areas adjoining the former unit areas, the unit areas each of which adjoins at least two other unit areas.
On the other hand, according to the technique stated in the paper entitled "Path Search Algorithm based on Hierarchical Expression of Road System and Application to Map Information Processing System", as illustrated in FIG. 15A, road data are successively hierarchized into a plurality of hierarchies such as express highways, national roads and small local roads. In each of the hierarchies thus mentioned, a closed area (block) surrounded with and comprising roads of higher hierarchy is managed as the lower-level block of that block of the higher hierarchy. Herein, the path is searched for every block and in a stepwise manner from the block of the lower hierarchy to the block of the higher hierarchy. Besides, in the path search, the path extending to the higher hierarchy is searched for from both the road nearest the point of departure and the road nearest the final destination point.
With the technique disclosed in the official gazette of Japanese Patent Application Laid-open No. 306400/1990, objects to be searched for can be limited. Since, however, roads are omitted, this technique poses the problem that an appropriate path cannot be selected.
By way of example,consider a case where an express highway joining the point of departure and the destination point exists as shown in FIG. 14B. In this case, the express highway extends, slightly, out of the set search area, and since it is not continuous within the search area, it cannot be selected. Thus, there is a high possibility that the more preferable path will fail to be selected notwithstanding that express highways, national roads and general roads are usually more suitable for travels in the order mentioned.
Meanwhile, the omission of the roads is reduced, when the size of each unit area is increased, but this leads to an increase in the number of objects to be searched.
On the other hand, the technique stated in the paper entitled "Path Search Algorithm based on Hierarchical Expression of Road System and Application to Map Information Processing System" has problems concerning difficulty in maintenance of road data.
More specifically, as illustrated in FIG. 15B, in a case where a road has been added or deleted at any hierarchical level other than the lowermost level, the block which belongs to the lower hierarchy of the block of the added or deleted road must be reorganized by the division of the single block or the mergence of the blocks.
Another problem is that the identification of the adjacent blocks is difficult because the area of the individual management blocks are nonuniform, and the numbers of the adjacent blocks usually becomes nonuniform.
Consequently, in a case where the map information processing system guides the vehicle during the running thereof by displaying the map on a display unit, it is difficult to scroll a screen and display the next block with the movement of the vehicle. Therefore, the technique used in this system is not suited for use on vehicles.
Moreover, the roads are not managed for extending blocks of the same hierarchy, but the path extending to the road of higher level is searched for every block, followed by the path search in the higher hierarchy. A problem is thus presented, when the multilevel crossing between the road of higher level and the road of lower level is existent, the connection of the lower-level road common to the blocks is lost. In a case as shown in FIG. 15C where the point of departure and the destination point have been set on the road which bridges the blocks and which forms the multilevel crossing with the higher-level road being the boundary of these blocks, the path containing such a road cannot be searched for in spite of it being the optimum path.